package review;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Ointerview {
	/**
	 * You have two arrays src, tgt, 
	 * containing two permutations of the numbers 0..n-1. 
	 * You would like to rearrange src so that it equals tgt. 
	 * The only allowed operations is 
	 * ???swap a number with 0???, e.g. {1,0,2,3} -> {1,3,2,0} (???swap 3 with 0???). 
	 * Write a program that prints to stdout the list of required operations
	 * @param src
	 * @param tgt
	 */
	public void rearrange(int[] src, int[] tgt ){
		int zeroPositionSrc = findTargetPosition(src, 0);
		for(int i = 0 ; i < src.length-1 ; i++){
			if(src[i] == 0) continue;
			if(src[i] == tgt[i]) continue;
			int newPo = findTargetPosition(tgt, src[i]);
			swap(src, zeroPositionSrc, newPo);
			printArray(src);
			swap(src, i, newPo);
			zeroPositionSrc = newPo;
			printArray(src);
		}
	}

	private int  findTargetPosition(int[] list, int value){
		int i = -1;
		while(list[++i] != value);
		return i;
	}

	private void swap(int[] list, int index1, int index2){
		int temp = list[index1];
		list[index1] = list[index2];
		list[index2] = temp;
	}

	private void printArray(int[] list){
		for(int i = 0 ; i < list.length ; i++){
			System.out.print(list[i] + " ");
		}
		System.out.println();
	}
	
	/**
	 * Convert sorted list to balanced binary search tree
	 * 
	 * @param iter
	 * @param start
	 * @param end
	 * @return
	 */
	public Node convertSortedListToBalancedTree(Iterator<Integer> iter, int start, int end){
		if(start > end) return null;
		int mid = start + (end-start) / 2;//same as (start+end)/2, avoids overflow
		Node left = convertSortedListToBalancedTree(iter, start, mid-1);
		Node node = new Node();
		if(iter.hasNext()){
			node.value = iter.next();
		}else return null;
		Node right = convertSortedListToBalancedTree(iter, mid+1, end);
		node.left = left; node.right = right;
		return node;
	}
	/**
	 * traverse the tree in in-order
	 * @param node
	 */
	public static void traverse(Node node){
		if(node == null) return;
		traverse(node.left);
		System.out.println(node.value);
		traverse(node.right);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Ointerview tryy = new Ointerview();
		tryy.rearrange(new int[]{1,3,2,0,4}, new int[]{0,1,2,4,3});
		LinkedList<Integer> list = new LinkedList<Integer>();
		for(int i = 0 ; i < 15 ; i++) list.add(i+1);
		Iterator<Integer> iter = list.iterator();
		Node root = tryy.convertSortedListToBalancedTree(iter, 0, 15);
		Ointerview.traverse(root);
		
		
		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		queue.add(1);
		queue.add(2);
		System.out.println(queue.peek());
	}
	
	class Node{
		public int value;
		public Node left, right;
	}

}
